//************************************************************
//    > File Name: merge_sort.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月13日 16:58:13
//***********************************************************
//lintcode #464
#include<bits/stdc++.h>
using namespace std;
void merge_core(vector<int>& arr,int begin,int mid,int end){
	int i,j,k=end-begin;
	vector<int> tmp(k,0);
	for(i=mid,j=end;i!=begin && j!=mid;)
		tmp[--k]=(arr[i-1]>arr[j-1]?arr[--i]:arr[--j]);
	for(;i!=begin;tmp[--k]=arr[--i]);
	for(;j!=mid;tmp[--k]=arr[--j]);
	for(i=begin,k=0;i<end;arr[i++]=tmp[k++]);
}
void merge_sort(vector<int>& arr,int begin,int end)
{
	if(end-begin<2) return;
	int mid=(begin+end)>>1;
	merge_sort(arr,begin,mid);
	merge_sort(arr,mid,end);
	merge_core(arr,begin,mid,end);
}
int main()
{
	vector<int> a;
	a.push_back(6);
	a.push_back(4);
	a.push_back(8);
	a.push_back(2);
	a.push_back(9);
	a.push_back(3);
	a.push_back(7);
	merge_sort(a,0,a.size());
	for(int i=0;i<a.size();i++)
		cout<< a[i] <<" ";
	cout<<endl;
	return 0;
}
